/**
 * 836. 矩形重叠
 * https://leetcode-cn.com/problems/rectangle-overlap/
 */
public class Solutions_836 {
    public static void main(String[] args) {
//        int[] rec1 = {0, 0, 2, 2}, rec2 = {1, 1, 3, 3};  // output: true
        int[] rec1 = {0, 0, 1, 1}, rec2 = {1, 0, 2, 1};  // output: false

        boolean result = isRectangleOverlap(rec1, rec2);
        System.out.println(result);
    }

    /**
     * 反证法
     * 两个矩形重叠的可能性一定多于不重叠的可能性
     * 在固定住 rec1 的情况下，rec2 与 rec1 保持不重叠的可能，只有 4 种情况。
     * 题目说明了矩形是正放的，即保证了给定左下角坐标 [rec1[0], rec1[1]]，
     * 右上角坐标 [rec1[2], rec1[3]] 的情况下，可以知道
     * 左上角坐标为左下角的 x 轴，右上角的 y 轴，即 [rec1[0], rec1[3]]
     * 右下角坐标为右上角的 x 轴，左下角的 y 轴，即 [rec1[2], rec1[1]]
     * 且题目说明了，边和角接触不构成重叠，所以坐标大于等于的情况，两个矩形不重叠
     */
    public static boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // 1. rec2 在 rec1 的上方，即 rec2 的左下角的 y 轴大于等于 rec1 的左上角的 y 轴
        if (rec2[1] >= rec1[3]) {
            return false;
        }
        // 2. rec2 在 rec1 的下方，即 rec2 的左上角的 y 轴小于等于 rec1 的左下角的 y 轴
        if (rec2[3] <= rec1[1]) {
            return false;
        }
        // 3. rec2 在 rec1 的左边，即 rec2 的右上角的 x 轴小于等于 rec1 的左上角的 x 轴
        if (rec2[2] <= rec1[0]) {
            return false;
        }
        // 4. rec2 在 rec1 的右边，即 rec2 的左上角的 x 轴大于等于 rec1 的右上角的 x 轴
        if (rec2[0] >= rec1[2]) {
            return false;
        }
        // 除了以上四种情况，两个矩形都是相交重叠的
        return true;
    }
}
